package com.da.javatest.leetCode2;

public class Code513 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(1);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        t1.left = t2;
        t1.right = t3;
        //t3.left = t4;
        System.out.println(new Code513().findBottomLeftValue(t1));
    }

    private int maxDeep = 0, deep = 1, result;

    public int findBottomLeftValue(TreeNode root) {
        if (maxDeep == 0) {
            maxDeep = getDeep(root);
        }
        if (deep == maxDeep) {
            result = root.val;
            deep = -99;
        }
        if (root.left != null) {
            deep++;
            findBottomLeftValue(root.left);
            deep--;
        }
        if (root.right != null) {
            deep++;
            findBottomLeftValue(root.right);
            deep--;
        }
        return result;
    }

    private int getDeep(TreeNode root) {
        return root == null ? 0 : Math.max(getDeep(root.left), getDeep(root.right)) + 1;
    }
}
